1. Field of the Invention
The present invention relates to a system and method for providing a congestion optimized address resolution protocol for wireless ad-hoc networks. More particularly, the present invention relates to a system and method for providing a congestion optimized address resolution protocol for wireless ad-hoc networks without a wireline interface. The present invention also relates to a system and method for enabling a node on a wireless ad-hoc network to issue an address resolution protocol request without the need to broadcast the request to a plurality of other nodes on the wireless ad-hoc network, to thus minimize the amount of traffic on the network necessary to handle the request. The present invention further relates to a system and method for data routing in an ad-hoc network where optimum mobile node-to-IAP links are constantly changing, and more particularly, to a system and method for modifying an address resolution protocol (ARP) mechanism to assign a unique media access control (MAC) address for mobile node's IAP, such that frames addressed with this unique MAC address are routed by medium-layer routing protocols to the node's associated IAP at the time the frame is sent.
2. Description of the Related Art
In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed for use by the military. In this type of network, each user terminal is capable of operating as a base station or router for the other user terminals, thus eliminating the need for a fixed infrastructure of base stations. Accordingly, data packets being sent from a source mobile node to a destination mobile node are typically routed through a number of intermediate mobile nodes before reaching the destination mobile node. Details of an ad-hoc network are set forth in U.S. Pat. No. 5,943,322 to Mayor, the entire content of which is incorporated herein by reference.
More sophisticated ad-hoc networks are also being developed which, in addition to enabling user terminals to communicate with each other as in a conventional ad-hoc network, further enable user terminals, also referred to as subscriber devices, to access a fixed network and thus communicate with other user terminals, such as those on the public switched telephone network (PSTN), and on other networks such as a local area network (LAN) and the Internet. Details of these types of ad-hoc networks are described in U.S. patent application Ser. No. 09/897,790 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, filed on Jun. 29, 2001, and in U.S. patent application Ser. No. 09/815,157 entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, filed on Mar. 22, 2001, and in U.S. patent application Ser. No. 09/815,164 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, filed on Mar. 22, 2001, the entire content of each being incorporated herein by reference.
Address Resolution Protocol (ARP) is a protocol for mapping an Internet Protocol address (IP address) to a physical machine address that is recognized in a local network, such as a LAN. For example, in IP Version 4, which is the most common level of IP in use today, an address is 32 bits long. In an Ethernet local area network, however, addresses for attached devices are 48 bits long. The physical machine address is also commonly referred to as a Media Access Control or MAC address. A table, usually called the ARP cache, is used to maintain a correlation between each MAC address and its corresponding IP address. ARP provides the protocol rules for making this correlation and providing address conversion in both directions, that is, from IP address to MAC address and vice-versa.
ARP functions in the following manner. When an incoming packet destined for a host machine on a particular LAN arrives at a gateway on the LAN, the gateway requests that the ARP program find a physical host or MAC address that matches the IP address. The ARP program looks in the ARP cache at the gateway and, if it finds the MAC address, provides the MAC address so that the packet can be converted and formatted as appropriate and sent to the machine. If no entry is found for the IP address in the ARP cache, the ARP program broadcasts a request packet in a special format to all the machines on the LAN to see if any machine recognizes that IP address as being associated with its MAC address. A machine that recognizes the IP address as its own returns an affirmative reply to the ARP program. A machine configured to respond to requests for an IP addresses other than its own, for which it is said to proxy, returns an affirmative reply if it recognizes the IP address as one for which it is so configured. In response, the ARP program updates the ARP cache for future reference, and then sends the packet to the machine having the MAC address associated with the IP address for which the packet is intended. Examples of conventional ARP techniques performed in asynchronous transfer mode (ATM) networks employing LANs are described in a publication by M. Laubach and J Halpern entitled “Classical IP and ARP over ATM”, IETF RFC 2225, April, 1998, in a publication by Jill Kaufman entitled “ATM Forum Education Corner”, ATM Forum, 2001, and in a publication by Rajeev Gupta entitled “The ‘Glue’ of Networks: Looking at IP over ATM”, ATM Forum, 2001, the entire contents of each of these documents is incorporated herein by reference.
Although the process described above is suitable for use with wired networks and broadcast wireless, the process is not suitable for use in an ad-hoc wireless network. Specifically, in an ad-hoc wireless network, when the ARP of a node causes a broadcast of the ARP request packet to all the nodes on the wireless network, such a broadcast could flood the radio network since it would be required to be repeated by every node to ensure completeness.
The MANET working group within the IETF is evaluating techniques in which to accomplish the delivery of such broadcast messages from a node in a wireless LAN. For example, the message can be via a broadcast of the IP address to all nodes on the network, or via a single hop broadcast to only neighboring nodes. In the case in which the message is broadcast to all nodes on the network, the amount of radio traffic generated on the network is enormous because each node must insure that its neighbors receive the message. Although certain techniques can be used to reduce this overhead, there is no mechanism for delivering a broadcast message toward a destination capable of resolving the ARP. Alternatively, in the single hop case, a node which is not directly connected to a node which can resolve the ARP request will never receive a reply. In addition, in either case, the reliability of the broadcast transfer can be severely impacted by the hidden terminal problem common in ad-hoc networks, as well as the near/far problem in which a node near to a node receiving a signal from a more distant node inadvertently transmits to the near node and thus destroys the ongoing reception from the distant node. A hidden terminal is a node which is out of range of a transmitting node and can therefore destroy an ongoing reception. This effect is particularly detrimental to broadcast transmissions which do not require a clear-to-send operation by the receiving node. Without the clear to send, the hidden terminal has no knowledge that a transmission is occurring and is free to attempt a transmission. An example of a non-broadcast multi-access subnetwork (NBMA) is described in a publication by J. Luciani et al. entitled “NBMA Next Hop Resolution Protocol (NHRP)”, IETF RFC 2332, April 1998, the entire contents of which is incorporated herein by reference.
Accordingly, a need exists for a system and method for improving the manner in which ARP is performed on wireless ad-hoc networks.
Furthermore, generally all of the nodes in a wireless ad-hoc peer-to-peer network provide certain similar core services and functionality, although they can each provide different functions relating to their specific purpose and application (e.g. if they are an access point, wireless router, and so on). Therefore peer-to-peer networks distinguish themselves from infrastructure networks where one or more nodes offer a superset of the functionality of the rest of the network. Infrastructure nodes in these networks typically can handle Dynamic Host Configuration Protocol (DHCP), Address Resolution Protocol (ARP), as well as other services that depend on broadcast traffic. DHCP is defined by IETF RFC 2131 and 2132, which are incorporated herein by reference, and is used by a client node to automatically obtain network settings from a central server. These network settings include the client's IP address, the address of Domain Name Servers (DNS), the IP address of default gateways, and many other network settings. Address resolution protocol is defined by STD 0037 and RFC 0826, which are incorporated herein by reference, and is used by a network node to map IP addresses to MAC addresses so IP traffic can be delivered to specific hardware.
These infrastructure nodes are normally discovered by broadcast traffic advertisements from their client nodes in a network, however peer-to-peer networks typically do not contain specialized infrastructure nodes. The IEEE 802.11 standard offers a peer-to-peer mode in addition to an infrastructure mode. Details of the 802.11 standards are set forth in ISO/IEC 8802-11, ANSI/IEEE 802.11 “Information Technology—Telecommunications and Information Exchange Between Systems—Local and Metropolitan Area Network Specific Requirements”, Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications, the entire contents of which being incorporated herein by reference. Also, a description of the 802.11 standard is found in a book by Bob O'Hara and Al Petrick entitled IEEE 802.11 Handbook: A Designer's Companion, IEEE, 1999, the entire contents of which being incorporated herein by reference.
These packet-switched networks can operate across many different kinds of physical hardware by using network-layer routers, such as Internet protocol (IP) routers, with multiple hardware interfaces at junctions where the different hardware mediums must communicate. In the case of fully connected multiple-access hardware mediums, such as CSMA-CD LAN's, where all nodes can directly communicate to all other nodes via hardware broadcasts, media converters can also be inserted into the network to operate below the network layer and pass hardware frames between two different mediums, such as with a 10base2-to-10baseT media converter. In this manner, a media converter can allow a single network-layer routing domain to span multiple hardware media.
However, in an ad-hoc networking system, all routing is done below the network layer since frames in the unified network layer sub-net may be intended for nodes within either the media, wired or wireless network. Therefore, routing methods must be adapted to cross any media junctures below the network layer. However, a media converter would not fit the need because the wireless medium is highly disconnected. That is, nodes in the wireless network may not hear frames from other nodes that are geographically or electrically distant, or occupy different data channels at the time of transmission. In certain ad-hoc networks, intelligent access points (IAP's) are connected to bridge the wired and wireless media, as network efficiency dictates that there be many diverse access points to the wired network. Details of these requirements are described in U.S. patent application Ser. Nos. 09/897,790, 09/815,157 and 09/815,164, referenced above.
Because the wireless network is not fully connected, the IAP's act as proxies rather than as media converters. Whereas a LAN media converter would hear all frames from all nodes on one medium and directly replicate them on the opposing medium, frames that must cross from the wireless medium to the wired medium in an ad-hoc network are medium-addressed directly to an access point below the network layer to ensure delivery, since the source of the frame may not be within direct transmission range of an access point. In such cases, broadcast services and address resolution protocol (ARP) are handled through special tunneling mechanisms, such as address resolution protocol. Unicast frames that must cross the media carry unicast addressing, particular to the given medium, that specifies a particular IAP.
As noted, address resolution within the ad-hoc network is difficult due to the replacement of traditional LAN components with a wireless network. Whereas in a LAN, ARP may broadcast a request packet for unknown addresses with little impact, in a wireless network such broadcasts could flood the radio network. As disclosed in U.S. Provisional Patent Application Ser. No. 60/357,645 to Whitehill et al. referenced above, modifications to the use of ARP satisfies the broadcast concerns of address resolution issues within ad-hoc networks, however the mobility of nodes in the network results in a need for yet further modifications.
Node mobility poses additional problems for traditional ARP uses, as address resolutions made by ARP are generally cached. Cached address resolutions work well for wired-to-wired or wireless-to-wireless unicast communications, as it reduces the need to resolve every network packet individually. Network addresses are resolved to medium addresses once, then cached for future network packets. In a typical implementation, this cache may have an expiration timeout on the order of 20-120 minutes. Upon timeout, a given network address will be re-resolved to ensure reliable resolution for situations where network addresses of given nodes change periodically, such as the case with a DHCP-managed network. When a wireless node resolves network addresses of devices on the wired medium, a medium address is determined that correlates to the node's associated IAP and which is presumed to be the “best” media bridge for the node to use. The best IAP may be selected based on bandwidth, spectral efficiency, or other reasons specific to the network. To provide this functionality, the ARP mechanism is implemented in such a way as to offer the medium address of a node's associated IAP when resolving network addresses of wired nodes. However, given node mobility, the best IAP may not be static for a given mobile node. In such a network, IAP associations may be formed and broken at a higher rate than the ARP expiration timeout would correct for. While the wireless network might allow routing to less-appropriate IAP's, the network would not operate very efficiently. Furthermore, security issues might not allow a non-associated IAP to proxy for a given wireless node.
Accordingly, in addition to an existing need for a system and method for improving the manner in which ARP is performed on wireless ad-hoc networks, a need exists for a system and method for modifying the ARP mechanism to assign a medium address for a mobile node's associated IAP in which the optimum IAP is targeted.